package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC134 {


    public int canCompleteCircuit(int[] gas, int[] cost) {
        for (int i = 0; i < gas.length; i++) {
            if (canTravel(gas, cost, i, i, 0)) {
                return i;
            }
        }

        return -1;
    }

    boolean canTravel(int[] gas, int[] cost, int startIndex, int curIndex, int lastReserveGas) {
        int nextIndex = (curIndex + 1) % cost.length;
        lastReserveGas = lastReserveGas + gas[curIndex] - cost[curIndex];

        if (lastReserveGas < 0) {
            return false;
        }

        if (nextIndex == startIndex) {
            return true;
        }

        return canTravel(gas, cost, startIndex, nextIndex, lastReserveGas);
    }

    public static void main(String[] args) {
        LC134 an = new LC134();
        int[] gas = InputUtil.toIntegerArray("[1,2,3,4,5]");
        int[] cost = InputUtil.toIntegerArray("[3,4,5,1,2]");
        System.out.println(an.canCompleteCircuit(gas, cost));
        //        System.out.println(an.canTravel(gas, cost, 4, 4, 0));
    }
}
